
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1624. -- [Usaco2008 Open] Clear And Present Danger -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1624: [Usaco2008 Open] Clear And Present Danger</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>137&nbsp;&nbsp;<span class=green>Solved: </span>101<br>[<a href='submitpage.php?id=1624'>Submit</a>][<a href='problemstatus.php?id=1624'>Status</a>][<a href='bbs.php?id=1624'>Discuss</a>]</center><h2>Description</h2><div class=content>Farmer John is on a boat seeking fabled treasure on one of the N
(1 <= N <= 100) islands conveniently labeled 1..N in the Cowribbean
Sea.

The treasure map tells him that he must travel through a certain
sequence A_1, A_2, ..., A_M of M (2 <= M <= 10,000) islands, starting
on island 1 and ending on island N before the treasure will appear
to him. He can visit these and other islands out of order and even
more than once, but his trip must include the A_i sequence in the
order specified by the map.

FJ wants to avoid pirates and knows the pirate-danger rating (0 <=
danger <= 100,000) between each pair of islands. The total danger
rating of his mission is the sum of the danger ratings of all the
paths he traverses.

Help Farmer John find the least dangerous route to the treasure
that satisfies the treasure map's requirement.

给出一个要访问的点的序列，但在实际走的时候，你可以经过某些中转点来进行访问. 
再给出任两点之间的危险值，求你在走的过程中危值值的总和是多少. 
</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Line i+1 describes the i_th island FJ must visit with
        a single integer: A_i

* Lines M+2..N+M+1: Line i+M+1 contains N space-separated integers
        that are the respective danger rating of the path between
        island i and islands 1, 2, ..., and N, respectively. The ith
        integer is always zero.

</div><h2>Output</h2><div class=content>* Line 1: The minimum danger that Farmer John can encounter while
        obtaining the treasure.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 4<br />
1<br />
2<br />
1<br />
3<br />
0 5 1<br />
5 0 2<br />
1 2 0<br />
<br />
INPUT DETAILS:<br />
<br />
There are 3 islands and the treasure map requires Farmer John to<br />
visit a sequence of 4 islands in order: island 1, island 2, island<br />
1 again, and finally island 3. The danger ratings of the paths are<br />
given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have<br />
danger ratings of 5, 2, and 1, respectively.<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>7<br />
<br />
OUTPUT DETAILS:<br />
<br />
He can get the treasure with a total danger of 7 by traveling in<br />
the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement<br />
(1, 2, 1, and 3) is satisfied by this route. We avoid the path<br />
between islands 1 and 2 because it has a large danger rating.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1624'>Submit</a>][<a href='problemstatus.php?id=1624'>Status</a>][<a href='bbs.php?id=1624'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
